package org.example.myleet.p1606;

import java.util.*;

public class Solution {
    public List<Integer> busiestServers(int k, int[] arrival, int[] load) {
        //可用服务器的有序集合，用于在log2(k)的复杂度情况下找到目标服务器
        TreeSet<Server> availableServerSet = new TreeSet<>(new Comparator<Server>() {
            @Override
            public int compare(Server o1, Server o2) {
                return o1.getNum() - o2.getNum();
            }
        });
        //保存所有服务器的状态
        Server[] servers = new Server[k];
        for (int i = 0; i < k; ++i) {
            servers[i] = new Server(i);
            availableServerSet.add(servers[i]);
        }
        //记录在忙的服务器，按下一个空闲时刻从近到远排序
        PriorityQueue<Server> busyServerQueue = new PriorityQueue<>(new Comparator<Server>() {
            @Override
            public int compare(Server o1, Server o2) {
                return o1.nextIdle - o2.nextIdle;
            }
        });
        //处理每一个请求
        for (int i = 0; i < arrival.length; ++i) {
            //下面根据当前时刻arrival[i]释放已经处理完的请求的服务器到可用服务器有序列表中，此处复杂度不超过n*log2(k)
            while (!busyServerQueue.isEmpty() && busyServerQueue.peek().nextIdle <= arrival[i]) {
                Server idleServer = busyServerQueue.poll();
                availableServerSet.add(idleServer);
            }
            //根据题意请求被打到的目标服务器
            Server server = servers[i % k];
            //根据目标服务器在可用服务器有序列表中的位置，查询到距离目标服务器最近的可用服务器，时间复杂度log2(k)
            Server nextServer = availableServerSet.ceiling(server);
            //但是要注意可能已经到达列表尾部，由于服务器按环形排序，因此若队列不为空则取出第一个
            if (null == nextServer && !availableServerSet.isEmpty()) {
                nextServer = availableServerSet.first();
            }
            if (null != nextServer) {
                //如果有空闲服务器，则处理这个请求，更新服务器的下一个空闲时间，从可用队列中移除并添加到忙的服务器堆中
                //时间复杂度2*log2(k)
                nextServer.setNextIdle(arrival[i] + load[i]);
                nextServer.increaseRequestCount();
                availableServerSet.remove(nextServer);
                busyServerQueue.offer(nextServer);
            }
            //否则没有空闲服务器，请求被丢弃
        }
        //所有请求已经处理完毕，时间复杂度(n+3)*log2(k)，下面是找出处理请求最多的服务器列表，时间复杂度n，总复杂度O(n + n*log2(k))
        List<Integer> result = new ArrayList<>(k);
        int maxRequestCount = 0;
        for (Server server : servers) {
            if (maxRequestCount < server.getRequestCount()) {
                maxRequestCount = server.getRequestCount();
                result.clear();
                result.add(server.getNum());
            } else if (maxRequestCount == server.getRequestCount()) {
                result.add(server.getNum());
            }
        }
        return result;
    }

    static class Server {
        //服务器编号
        private final int num;

        //服务器处理请求个数
        private int requestCount;

        //服务器下一个空闲时刻
        private int nextIdle;

        public Server(int num) {
            this.num = num;
            requestCount = 0;
            nextIdle = 0;
        }

        public int getNum() {
            return num;
        }

        public int getRequestCount() {
            return requestCount;
        }

        public void increaseRequestCount() {
            ++requestCount;
        }

        public long getNextIdle() {
            return nextIdle;
        }

        public void setNextIdle(int nextIdle) {
            this.nextIdle = nextIdle;
        }

        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder("Server{");
            sb.append("num=").append(num);
            sb.append(", requestCount=").append(requestCount);
            sb.append(", nextIdle=").append(nextIdle);
            sb.append('}');
            return sb.toString();
        }
    }
}
